#include "basic/ready_list.h"
#include "generic/utilities.h"
#include "generic/logger.h"
#include "basic/data_dep.h"

namespace opt_sched {

ReadyList::ReadyList(DataDepGraph* dataDepGraph, Priorities prirts) {
  prirts_ = prirts;
  prirtyLst_ = NULL;

  crtclPathBits_ = scsrCntBits_ = ltncySumBits_ = nodeID_Bits_ = \
      fileSchedOrderBits_ = 0;

  // Calculate the number of bits needed to hold the maximum upper bound.
  if (prirts_.criticalPath) {
    maxCrtclPath_ = dataDepGraph->GetRootInst()->GetCrntLwrBound(DIR_BKWRD);
    crtclPathBits_ = Utilities::clcltBitsNeededToHoldNum(maxCrtclPath_);
  }

  if (prirts_.successorCount) {
    // Calculate bits needed to hold the maximum number of successors.
    maxScsrCnt_ = dataDepGraph->GetMaxScsrCnt();
    scsrCntBits_ = Utilities::clcltBitsNeededToHoldNum(maxScsrCnt_);
  }

  if (prirts_.latencySum) {
    // Calculate bits needed to hold the maximum latency sum.
    maxLtncySum_ = dataDepGraph->GetMaxLtncySum();
    ltncySumBits_ = Utilities::clcltBitsNeededToHoldNum(maxLtncySum_);
  }

  if (prirts_.nodeID) {
    maxNodeID_ = dataDepGraph->GetInstCnt() - 1;
    nodeID_Bits_ = Utilities::clcltBitsNeededToHoldNum(maxNodeID_);
  }

  if (prirts_.fileSchedOrder) {
    maxFileSchedOrder_ = dataDepGraph->GetInstCnt() - 1;
    fileSchedOrderBits_ = Utilities::clcltBitsNeededToHoldNum(
        maxFileSchedOrder_);
  }

  #ifdef IS_DEBUG
    uint16_t totKeyBits = crtclPathBits_ + scsrCntBits_ + ltncySumBits_ +
                          nodeID_Bits_ + fileSchedOrderBits_;
    assert(totKeyBits <= 8 * sizeof(unsigned long));
    #ifdef IS_DEBUG_READY_LIST2
      Logger::Info("The ready list key size is %d bits", totKeyBits);
    #endif
  #endif

  prirtyLst_ = new PriorityList<SchedInstruction>;
  if (prirtyLst_ == NULL) Logger::Fatal("Out of memory.");

  latestSubLst_ = new LinkedList<SchedInstruction>;
  if (latestSubLst_ == NULL) Logger::Fatal("Out of memory.");
}

ReadyList::~ReadyList() {
  Reset();
  if (prirtyLst_) delete prirtyLst_;
  if (latestSubLst_) delete latestSubLst_;
}

void ReadyList::Reset() {
  prirtyLst_->Reset();
  latestSubLst_->Reset();
}

void ReadyList::CopyList(ReadyList* othrLst) {
  assert(prirtyLst_->GetElmntCnt() == 0);
  assert(latestSubLst_->GetElmntCnt() == 0);
  assert(othrLst != NULL);
  prirtyLst_->CopyList(othrLst->prirtyLst_);
}

unsigned long ReadyList::CmputKey_(SchedInstruction* inst) {
  unsigned long key = 0;
  int16_t keySize = 0;

  if (prirts_.criticalPath) {
    if (prirts_.accountForRsrcs) {
      AddPrirtyToKey_(key,
                      keySize,
                      crtclPathBits_,
                      inst->GetCrntLwrBound(DIR_BKWRD),
                      maxCrtclPath_);
    } else {
      AddPrirtyToKey_(key,
                      keySize,
                      crtclPathBits_,
                      inst->GetCrtclPath(DIR_BKWRD),
                      maxCrtclPath_);
    }
  }

  if (prirts_.successorCount) {
    AddPrirtyToKey_(key,
                    keySize,
                    scsrCntBits_,
                    inst->GetScsrCnt(),
                    maxScsrCnt_);
  }

  if (prirts_.latencySum) {
    AddPrirtyToKey_(key,
                    keySize,
                    ltncySumBits_,
                    inst->GetLtncySum(),
                    maxLtncySum_);
  }

  if (prirts_.nodeID) {
    AddPrirtyToKey_(key,
                    keySize,
                    nodeID_Bits_,
                    maxNodeID_ - inst->GetNum(),
                    maxNodeID_);
  }

  if (prirts_.fileSchedOrder) {
    AddPrirtyToKey_(key,
                    keySize,
                    fileSchedOrderBits_,
                    maxFileSchedOrder_ - inst->GetFileSchedOrder(),
                    maxFileSchedOrder_);
  }

  return key;
}

void ReadyList::AddLatestSubLists(LinkedList<SchedInstruction>* lst1,
                                  LinkedList<SchedInstruction>* lst2) {
  assert(latestSubLst_->GetElmntCnt() == 0);
  if (lst1 != NULL) AddLatestSubList_(lst1);
  if (lst2 != NULL) AddLatestSubList_(lst2);
  prirtyLst_->ResetIterator();
}

void ReadyList::Print(std::ostream& out) {
  out << "\nReady List: ";
  for (SchedInstruction* crntInst = prirtyLst_->GetFrstElmnt();
       crntInst != NULL;
       crntInst = prirtyLst_->GetNxtElmnt()) {
    out << crntInst->GetNum() << ", ";
  }
}

void ReadyList::AddLatestSubList_(LinkedList<SchedInstruction>* lst) {
  assert(lst != NULL);

  #ifdef IS_DEBUG_READY_LIST2
    Logger::GetLogStream() << "Adding to the ready list: ";
  #endif

  // Start iterating from the bottom of the list to access the most recent
  // instructions first.
  for (SchedInstruction* crntInst = lst->GetLastElmnt();
       crntInst != NULL;
       crntInst = lst->GetPrevElmnt()) {
    // Once an instruction that is already in the ready list has been
    // encountered, this instruction and all the ones above it must be in the
    // ready list already.
    if (crntInst->IsInReadyList()) break;
    AddInst(crntInst);
    #ifdef IS_DEBUG_READY_LIST2
      Logger::GetLogStream() << crntInst->GetNum() << ", ";
    #endif
    crntInst->PutInReadyList();
    latestSubLst_->InsrtElmnt(crntInst);
  }

  #ifdef IS_DEBUG_READY_LIST2
    Logger::GetLogStream() << "\n";
  #endif
}

void ReadyList::RemoveLatestSubList() {
  #ifdef IS_DEBUG_READY_LIST2
    Logger::GetLogStream() << "Removing from the ready list: ";
  #endif

  for (SchedInstruction* inst = latestSubLst_->GetFrstElmnt();
       inst != NULL;
       inst = latestSubLst_->GetNxtElmnt()) {
    assert(inst->IsInReadyList());
    inst->RemoveFromReadyList();
    #ifdef IS_DEBUG_READY_LIST2
      Logger::GetLogStream() << inst->GetNum() << ", ";
    #endif
  }

  #ifdef IS_DEBUG_READY_LIST2
    Logger::GetLogStream() << "\n";
  #endif
}

void ReadyList::ResetIterator() {
  prirtyLst_->ResetIterator();
}

void ReadyList::AddInst(SchedInstruction* inst) {
  unsigned long key = CmputKey_(inst);
  prirtyLst_->InsrtElmnt(inst, key, true);
}

void ReadyList::AddList(LinkedList<SchedInstruction>* lst) {
  SchedInstruction* crntInst;

  if (lst != NULL)
    for (crntInst = lst->GetFrstElmnt();
         crntInst != NULL;
         crntInst = lst->GetNxtElmnt()) {
      AddInst(crntInst);
    }

  prirtyLst_->ResetIterator();
}

InstCount ReadyList::GetInstCnt() const {
  return prirtyLst_->GetElmntCnt();
}

SchedInstruction* ReadyList::GetNextPriorityInst() {
  return prirtyLst_->GetNxtPriorityElmnt();
}

void ReadyList::RemoveNextPriorityInst() {
  prirtyLst_->RmvCrntElmnt();
}

bool ReadyList::FindInst(SchedInstruction* inst, int& hitCnt) {
  return prirtyLst_->FindElmnt(inst, hitCnt);
}

void ReadyList::AddPrirtyToKey_(unsigned long& key,
                                int16_t& keySize,
                                int16_t bitCnt,
                                unsigned long val,
                                unsigned long maxVal) {
  assert(val <= maxVal);
  if (keySize > 0) key <<= bitCnt;
  key |= val;
  keySize += bitCnt;
}

} // end namespace opt_sched
